package algorithm_primary.studyClass.新手课程.二五翻转链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 衡孟浩
 * @date 2023/5/28 17:09
 * <p>
 * <p>
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 */
public class TestMain {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(4);
        listNode1.next.next.next.next = new ListNode(5);
        listNode1.next.next.next.next.next = new ListNode(6);
        reverseKGroup(listNode1, 2);
        ArrayList<Integer> arrayList = new ArrayList();
        arrayList.add(1);
    }


    public static ListNode reverseKGroup(ListNode head, int k) {

        // 比如  head = [1,2,3,4,5,6], k = 2   那么  第一次返回会返回  1，2
        ListNode end = getLastKNode(head, k);
        if (end == null) {
            return head;
        }
        // 第一次完成headnext记录当前操作的第一个是谁   比如第一次head就是 1  k=2 那么就把1记录下来
        ListNode headnext = head;
        // 记录下来当前操作最后一个对象的下一个指针   用作下一次的开头
        // 比如  [1,2,3,4,5,6], k = 2  getLastKNode返回也给2   那么下一次反转就是通过2的下一个也就是  3开始的
        ListNode start = end.next;
        // 反转  比如head = 1  end = 2   那么就是  反转前就是  1->2->3  反转后  就是  2->1->3
        head = reverse(head, end);

        while (start != null) {
            ListNode resta = start;
            end = getLastKNode(resta, k);
            if (end == null) {
                return head;
            }
            // 记录下一个应该操作的是谁
            start = end.next;
            reverse(resta, end);
            // 将上一次操作的对象的下一个指针指向这次操作的end
            // 比如 [1,2,3,4,5,6], k = 2  比如上一次操作过1了  那么链表就是  2->1->3->4->5->6
            // 那么  headnext = 1  而这次的end是4   经过这次的操作以后是这样的  2->1->4->3->5->6
            //  headnext.next = end这个操作就是为了让 1的下一个指针指向4
            headnext.next = end;
            // 将这次操作开始对象给headnext留作下次赋值
            headnext = resta;
        }
        return head;
    }


    /**
     * 获取当前第k个节点
     *
     * @param head
     * @param k
     * @return
     */
    private static ListNode getLastKNode(ListNode head, int k) {
        // 比如   head = [1,2,3,4,5], k = 2
        // 第一次  --k > 0 = true    head != null = true         head = 1
        // 经历whil的操作以后   head = 2    k = 1
        // 如果返回一个null那么说明 已经到了最后了并且是凑不齐的一组
        while (--k > 0 && head != null) {
            head = head.next;
        }
        return head;
    }

    /**
     * 1,2,3,4,5   3
     * pre = null    next = null  end = 4   start 1
     * next = 2   1->null pre = 1  head = 2
     * <p>
     * next = 3 2->1    pre = 2  head = 3
     * 2->1->3
     *
     * @param head
     * @param end
     * @return
     */
    private static ListNode reverse(ListNode head, ListNode end) {
        ListNode pre = null, next = null;
        end = end.next;
        ListNode start = head;
        while (end != head) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        start.next = end;
        // 返回的是最后操作的对象
        return pre;
    }
}
